{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #比特位计数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: countBits"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #比特位计数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个非负整数 <code>n</code><b>&nbsp;</b>，请计算 <code>0</code> 到 <code>n</code> 之间的每个数字的二进制表示中 1 的个数，并输出一个数组。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>n =<strong> </strong>2\n",
    "<strong>输出: </strong>[0,1,1]\n",
    "<strong>解释: \n",
    "</strong>0 --&gt; 0\n",
    "1 --&gt; 1\n",
    "2 --&gt; 10\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例&nbsp;2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>n =<strong> </strong>5\n",
    "<strong>输出: </strong><code>[0,1,1,2,1,2]\n",
    "</code><span style=\"white-space: pre-wrap;\"><strong>解释:</strong>\n",
    "</span>0 --&gt; 0\n",
    "1 --&gt; 1\n",
    "2 --&gt; 10\n",
    "3 --&gt; 11\n",
    "4 --&gt; 100\n",
    "5 --&gt; 101\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>说明 :</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>进阶:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>给出时间复杂度为&nbsp;<code>O(n*sizeof(integer))</code><strong>&nbsp;</strong>的解答非常容易。但你可以在线性时间&nbsp;<code>O(n)</code><strong>&nbsp;</strong>内用一趟扫描做到吗？</li>\n",
    "\t<li>要求算法的空间复杂度为&nbsp;<code>O(n)</code>&nbsp;。</li>\n",
    "\t<li>你能进一步完善解法吗？要求在C++或任何其他语言中不使用任何内置函数（如 C++ 中的&nbsp;<code>__builtin_popcount</code><strong>&nbsp;</strong>）来执行此操作。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" />注意：本题与主站 338&nbsp;题相同：<a href=\"https://leetcode-cn.com/problems/counting-bits/\">https://leetcode-cn.com/problems/counting-bits/</a></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [w3tCBm](https://leetcode.cn/problems/w3tCBm/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [w3tCBm](https://leetcode.cn/problems/w3tCBm/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBits(self, n: int) -> List[int]:\n",
    "        ans = []\n",
    "        for i in range(n + 1):\n",
    "            t = i\n",
    "            count = 0\n",
    "            while t != 0:\n",
    "                t &= (t - 1)\n",
    "                count += 1\n",
    "            ans.append(count)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBits(self, n: int) -> List[int]:\n",
    "        res = [0]\n",
    "        if n == 0:\n",
    "            return res\n",
    "        temp = 1\n",
    "        while(temp <= n):\n",
    "            res += [i+1 for i in res]\n",
    "            temp = temp << 1\n",
    "        return res[:n+1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBits(self, n: int) -> List[int]:\n",
    "        res=[0]\n",
    "        k=0\n",
    "        temp=1\n",
    "        while temp<n+1:\n",
    "            temp*=2\n",
    "            k+=1\n",
    "            res.extend([1+i for i in res])\n",
    "        return res[:n+1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBits(self, n: int) -> List[int]:\n",
    "        if n <= 2:\n",
    "            return [0, 1, 1][:n+1]\n",
    "        left, right, mid = 0, n, -1\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            if 2 ** mid == n:\n",
    "                break\n",
    "            elif 2 ** mid < n:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        res = [0, 1]\n",
    "        for i in range(1, mid+1):\n",
    "            res.extend([res[j]+1 for j in range(2**i)])\n",
    "        return res[:n+1]\n",
    "            \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    _dp=[0]\n",
    "    def countBits(self, n: int) -> List[int]:\n",
    "        dp=self._dp\n",
    "        while len(dp)<n+1:\n",
    "            dp.append(dp[len(dp)>>1]+int(len(dp)&1))\n",
    "            #print(x,x>>1,x&1,dp[x>>1],dp[x>>1]+x&1,dp)\n",
    "        return dp[:n+1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBits(self, n: int) -> List[int]:\n",
    "        r = []\n",
    "        for i in range(n+1):\n",
    "            r.append(bin(i).count(\"1\"))\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBits(self, n: int) -> List[int]:\n",
    "        h = []\n",
    "        for i in range(n+1):\n",
    "            h.append(bin(i).count('1'))\n",
    "        return h"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBits(self, n: int) -> List[int]:\n",
    "        if n ==0:return [0]\n",
    "        res =[0]\n",
    "        for i in range(1,n+1):\n",
    "            ans =0\n",
    "            while i!=0:\n",
    "                i= i&(i-1)\n",
    "                ans+=1\n",
    "            res.append(ans)\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBits(self, n: int) -> List[int]:\n",
    "        res = []\n",
    "        for i in range(n+1):\n",
    "            num = bin(i).count('1')\n",
    "            res.append(num)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBits(self, n: int) -> List[int]:\n",
    "        number = [0]\n",
    "        for i in range(1,n+1):\n",
    "            s = str(bin(i)).count(\"1\")\n",
    "            number.append(s)\n",
    "        return number\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBits(self, n: int) -> List[int]:\n",
    "        ans = [0]\n",
    "        for i in range(1, n + 1):\n",
    "            if (i & (i - 1)) == 0:\n",
    "                ans.append(1)\n",
    "            elif i % 2 == 0:\n",
    "                ans.append(ans[i // 2])\n",
    "            else:\n",
    "                ans.append(ans[i - 1] + 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBits(self, n: int) -> List[int]:\n",
    "        res = [0]\n",
    "        for i in range(1, n + 1):\n",
    "            res.append(res[i >> 1] + (i & 1))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBits(self, n: int) -> List[int]:\n",
    "        bits = [0]\n",
    "        highBit = 0\n",
    "        for i in range(1, n + 1):\n",
    "            if i & (i - 1) == 0:\n",
    "                highBit = i\n",
    "            bits.append(bits[i - highBit] + 1)\n",
    "        return bits\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBits(self, n: int) -> List[int]:\n",
    "        dic=[]\n",
    "        for i in range(n+1):\n",
    "            count=0\n",
    "            while i:\n",
    "                if i <=len(dic)-1:\n",
    "                    count+=dic[i]\n",
    "                    break\n",
    "                if i & 1:\n",
    "                    count+=1\n",
    "                i=i>>1\n",
    "            dic.append(count)\n",
    "        return dic\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBits(self, n: int) -> List[int]:\n",
    "        if n == 0:\n",
    "            return [0]\n",
    "        res = [0,1]\n",
    "        k = 1\n",
    "        for i in range(2, n+1):\n",
    "            if i >= 2**k and i < 2**(k+1):\n",
    "                res.append(res[i-2**k]+1)\n",
    "            else:\n",
    "                k += 1\n",
    "                res.append(1)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBits(self, n: int) -> List[int]:\n",
    "        ansarr = [0]\n",
    "        for i in range(1,n+1):\n",
    "            ansarr.append(ansarr[i//2]+i%2)\n",
    "        return ansarr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBits(self, n: int) -> List[int]:\n",
    "        result = []\n",
    "        for i in range(n+1):\n",
    "            count = 0\n",
    "            num = i\n",
    "            while num:\n",
    "                num = num & (num-1)\n",
    "                count += 1\n",
    "            result.append(count)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBits(self, n: int) -> List[int]:\n",
    "        bits = [0]\n",
    "        highBit = 0\n",
    "        for i in range(1, n + 1):\n",
    "            if i & (i - 1) == 0:\n",
    "                highBit = i\n",
    "            bits.append(bits[i - highBit] + 1)\n",
    "        return bits"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBits(self, n: int) -> List[int]:\n",
    "        res=[]\n",
    "        for v in range(n+1):\n",
    "            temp = str(bin(v)).count('1')\n",
    "            res.append(temp)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBits(self, n: int) -> List[int]:\n",
    "        \"\"\"\n",
    "        方法：最低有效位\n",
    "        \"\"\"\n",
    "        ans = [0] * (n + 1)\n",
    "        for i in range(1, n+1):\n",
    "            ans[i] = ans[i & (i-1)] + 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBits(self, n: int) -> List[int]:\n",
    "        nums=[]\n",
    "        for i in range(n+1):\n",
    "            num = 0\n",
    "            while i>0:\n",
    "                i &=i-1\n",
    "                num+=1\n",
    "            nums.append(num)\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBits(self, n: int) -> List[int]:\n",
    "        bits = [0]\n",
    "        for i in range(1, n + 1):\n",
    "            bits.append(bits[i >> 1] + (i & 1))\n",
    "        return bits\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBits(self, n: int) -> List[int]:\n",
    "        res = [0 for i in range(0, n+1)]\n",
    "        for num in range(0, n+1):\n",
    "            res[num] = res[num//2] + num%2\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBits(self, n: int) -> List[int]:\n",
    "        ansarr = [0]\n",
    "        for i in range(1,n+1):\n",
    "            ansarr.append(ansarr[i//2]+i%2)\n",
    "        return ansarr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBits(self, n: int) -> List[int]:\n",
    "        bits = [0]\n",
    "        for i in range(1, n + 1):\n",
    "            bits.append(bits[i >> 1] + (i & 1))\n",
    "        return bits\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBits(self, n: int) -> List[int]:\n",
    "        def compute(n: int):\n",
    "            ans = n & 1\n",
    "            while n:\n",
    "                ans += (n >> 1) & 1\n",
    "                n >>= 1\n",
    "            return ans\n",
    "        return [compute(i) for i in range(0, n+1)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBits(self, n: int) -> List[int]:\n",
    "        list = [0]\n",
    "        for i in range(1,n+1):\n",
    "            count = 0\n",
    "            x = i\n",
    "            while x!=0:\n",
    "                x = x&(x-1)\n",
    "                count += 1\n",
    "            list.append(count)\n",
    "        return list\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBits(self, n: int) -> List[int]:\n",
    "        dp = [0] * (n + 1)\n",
    "        for i in range(n+1):\n",
    "            dp[i] = dp[i >> 1] + (1 if i & 1 else 0)\n",
    "        return dp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBits(self, n: int) -> List[int]:\n",
    "        o=[]\n",
    "        for i in range(0,n+1):\n",
    "            res=0\n",
    "            while i:\n",
    "                res += i&1\n",
    "                i>>=1\n",
    "            o.append(res)\n",
    "        return o\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBits(self, n: int) -> List[int]:\n",
    "        if n == 0 or n == 1:\n",
    "            return list(range(n + 1))\n",
    "        \n",
    "        dp = [0] * (n + 1)\n",
    "        dp[1] = 1\n",
    "        for i in range(2, n+1):\n",
    "            dp[i] = dp[i >> 1] + (i & 1)\n",
    "        \n",
    "        return dp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBits(self, n: int) -> List[int]:\n",
    "        dp = [0] * (n+1)\n",
    "        for i in range(n+1):\n",
    "            if i % 2 == 1:\n",
    "                dp[i] = dp[i-1] + 1\n",
    "            else:\n",
    "                dp[i] = dp[i//2]\n",
    "\n",
    "        return dp \n",
    "           \n",
    "              "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBits(self, n: int) -> List[int]:\n",
    "        \"\"\"\n",
    "        方法：最低有效位\n",
    "        \"\"\"\n",
    "        ans = [0] * (n + 1)\n",
    "        for i in range(1, n+1):\n",
    "            ans[i] = ans[i & (i-1)] + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBits(self, n: int) -> List[int]:\n",
    "        bit = [0]*(n+1)\n",
    "        for i in range(1, n+1):\n",
    "            bit[i] = bit[i&(i-1)] + 1\n",
    "        return bit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBits(self, n: int) -> List[int]:\n",
    "        res = [0] * (n + 1)\n",
    "\n",
    "        for i in range(n + 1):\n",
    "            res[i] = res[i // 2] + (i % 2)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBits(self, n: int) -> List[int]:\n",
    "        # dp[i] 为 1的个数，如果是偶数，1的个数等于它的//2\n",
    "        # 如果是奇数，就比上一个偶数多1\n",
    "        dp = [0] * (n+1)\n",
    "        for i in range(1,n+1):\n",
    "            if i % 2 == 0:\n",
    "                dp[i] = dp[i//2]\n",
    "            else:                \n",
    "                dp[i] = dp[i-1] + 1\n",
    "        return dp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBits(self, n: int) -> List[int]:\n",
    "        \"\"\"\n",
    "        方法：最高有效位\n",
    "        \"\"\"\n",
    "        ans = [0] * (n + 1)\n",
    "        high_bit = 1\n",
    "        for i in range(1, n+1):\n",
    "            high_bit = i if i & (i - 1) == 0 else high_bit\n",
    "            ans[i] = ans[i - high_bit] + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBits(self, n: int) -> List[int]:\n",
    "            dp=[0]*(n+1) #dp[i]表示i的1个数\n",
    "            for i in range(1,n+1):\n",
    "                if i%2==0:\n",
    "                    dp[i]=dp[i>>1]         #偶数的话，最右边肯定是0，然后例如；2 10 4 100 就是右移的偶数\n",
    "                else:\n",
    "                    dp[i]=dp[i-1]+1        #奇数的话，是前一个数+1 例如3 11 2 10\n",
    "            return dp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBits(self, n: int) -> List[int]:\n",
    "        res = [0] * (n + 1)\n",
    "\n",
    "        for i in range(1, n + 1):\n",
    "            res[i] = res[i // 2] + (i % 2)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBits(self, n: int) -> List[int]:\n",
    "        nums = [0] * (n+1)\n",
    "        for i in range(n+1):\n",
    "            for j in range(32):\n",
    "                nums[i] += (i>>j) & 1\n",
    "\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBits(self, n: int) -> List[int]:\n",
    "        dp = [0] * (n + 1)\n",
    "        highBit = 0\n",
    "        for i in range(1, n + 1):\n",
    "            if i & (i - 1) == 0: # 说明i是2的整数幂\n",
    "                highBit = i\n",
    "            dp[i] = dp[i - highBit] + 1\n",
    "        return dp\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBits(self, n: int) -> List[int]:\n",
    "        bits = [0] * (n + 1)\n",
    "        for i in range(1, n + 1):\n",
    "            bits[i] =(bits[i & (i - 1)] + 1)\n",
    "        return bits\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBits(self, n: int) -> List[int]:\n",
    "        ret:list[int] = [0,1,1,2,1,2]\n",
    "        for i in range(6,n+1):\n",
    "            bits_str = str(bin(i))\n",
    "            nums_of_1 = bits_str.count('1')\n",
    "            ret.append(nums_of_1)\n",
    "        return ret[0:n+1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBits(self, n: int) -> List[int]:\n",
    "        dp = [0] * (n+1)\n",
    "        for i in range(1,n+1):\n",
    "            if i % 2 == 1:\n",
    "                dp[i] = dp[i-1] + 1\n",
    "            else:\n",
    "                dp[i] = dp[i//2]\n",
    "        return dp\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBits(self, n: int) -> List[int]:\n",
    "\n",
    "        ret = [0] * (n + 1)   \n",
    "        end, idx = 1, 1\n",
    "\n",
    "        while idx <= n:\n",
    "            for i in range(0, end):\n",
    "                if idx == n + 1:\n",
    "                    break\n",
    "                ret[idx] = ret[i] + 1\n",
    "                idx += 1\n",
    "                i += 1\n",
    "            end = end << 1\n",
    "        \n",
    "        return ret\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBits(self, n: int) -> List[int]:\n",
    "        if n == 0:\n",
    "            return [0]\n",
    "        \n",
    "        # 获取从0到11...1中1的个数\n",
    "        record = [0]\n",
    "        num = 1\n",
    "        while num <= (n+1)/2:\n",
    "            record = record + [i+1 for i in record]\n",
    "            num *= 2\n",
    "        if num < n + 1:\n",
    "            record = record + [record[j]+1 for j in range(n+1-num)]\n",
    "        return record"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBits(self, n: int) -> List[int]:\n",
    "        if n == 0:\n",
    "            return [0]\n",
    "        \n",
    "        # 获取从0到11...1中1的个数\n",
    "        record = [0]\n",
    "        num = 1\n",
    "        while num <= (n+1)/2:\n",
    "            record = record + [i+1 for i in record]\n",
    "            num *= 2\n",
    "        if num < n + 1:\n",
    "            record = record + [record[j]+1 for j in range(n+1-num)]\n",
    "        return record"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBits(self, n: int) -> List[int]:\n",
    "        ans = [0]\n",
    "        while len(ans) < n + 1:\n",
    "            temp = []\n",
    "            for num in ans:\n",
    "                temp.append(num + 1)\n",
    "            ans = ans + temp\n",
    "        return ans[:n + 1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBits(self, n: int) -> List[int]:\n",
    "        ans = [0]\n",
    "        for i in range(0,n+1):\n",
    "            j = 0\n",
    "            while 2**j<=n:\n",
    "                if i%(2**j)!=2**j-1:\n",
    "                   \n",
    "                    break\n",
    "                j += 1\n",
    "            ans.append(ans[i]+1-(j-1))\n",
    "        return ans[:-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBits(self, n: int) -> List[int]:\n",
    "        q = [0,1]\n",
    "        i = 1\n",
    "        while len(q)-1<n:\n",
    "            new_q = []\n",
    "            for v in q:\n",
    "                new_q.append(v+1)\n",
    "            q = q+new_q\n",
    "        return q[:n+1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBits(self, n: int) -> List[int]:\n",
    "        ans = [0]\n",
    "        length = 1\n",
    "        while length < n + 1:\n",
    "            ans = ans + [j + 1 for j in ans]\n",
    "            length *= 2\n",
    "        return ans[:n + 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def helper(self, n):\n",
    "        cnt = 0\n",
    "        while n:\n",
    "            print(n, n & 1)\n",
    "            if (n & 1) == 1:\n",
    "                cnt += 1\n",
    "            n = n >> 1\n",
    "        \n",
    "        return cnt \n",
    "    def countBits(self, n: int) -> List[int]:\n",
    "        res = []\n",
    "        for i in range(n+1):\n",
    "            res.append(self.helper(i))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBits(self, n: int) -> List[int]:\n",
    "        res = [0] * (n+1)\n",
    "        counter = 1\n",
    "        queue = [0]\n",
    "        bounds = [0] * (n+1)\n",
    "        bounds[0] = n + 1\n",
    "        while queue:\n",
    "            temp_queue = []\n",
    "            for start in queue:\n",
    "                base = 1\n",
    "                temp_bound = min(bounds[start], n + 1 - start)\n",
    "                while base < temp_bound:\n",
    "                    curr_idx = start + base\n",
    "                    res[curr_idx] = counter\n",
    "                    temp_queue.append(curr_idx)\n",
    "                    bounds[curr_idx] = base # set bound\n",
    "                    base *= 2\n",
    "            counter += 1\n",
    "            queue = temp_queue\n",
    "        return res\n",
    "\n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBits(self, n: int) -> List[int]:\n",
    "        def what(x):\n",
    "            tmp = 0\n",
    "            while x:\n",
    "                tmp += 1\n",
    "                x &= x-1\n",
    "            return tmp\n",
    "        res = []\n",
    "        for i in range(n+1):\n",
    "            a = what(i)\n",
    "            print(a)\n",
    "            res.append(a)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.array = [0,1]\n",
    "        while len(self.array)<10**5:\n",
    "            self.array = self.array + [i+1 for i in self.array]\n",
    "    \n",
    "    def countBits(self, n: int) -> List[int]:\n",
    "        return self.array[:n+1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBits(self, n: int) -> List[int]:\n",
    "        res = [0, 1]\n",
    "        if  n <= 1:\n",
    "            return res[:n+1]\n",
    "        rec = [1,2]\n",
    "        new_rec = [1,2,2,3]\n",
    "        n = n - 1\n",
    "        while n:\n",
    "            if rec:\n",
    "                res.append(rec[0])\n",
    "                rec = rec[1:]\n",
    "            else:\n",
    "                rec = new_rec\n",
    "                new_rec = rec + [ i + 1 for i in rec]\n",
    "                res.append(rec[0])\n",
    "                rec = rec[1:]\n",
    "            n -= 1\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBits(self, n: int) -> List[int]:\n",
    "        dp = [0] * (n + 1)\n",
    "        ans = [0]\n",
    "        for i in range(1, n + 1):\n",
    "            if i % 2 == 1:\n",
    "                dp[i] = dp[i - 1] + 1\n",
    "            else:\n",
    "                dp[i] = dp[i >> 1]\n",
    "            ans.append(dp[i])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBits(self, n: int) -> List[int]:\n",
    "        if n == 0: return [0]\n",
    "        if n == 1: return [0,1]\n",
    "\n",
    "        result = [0,1]\n",
    "        n_Bin = bin(n)\n",
    "        n_BinLen = len(n_Bin) - 2\n",
    "\n",
    "        for bit in range(1,n_BinLen+1):\n",
    "            if bit == 1:\n",
    "                pass\n",
    "            else:\n",
    "                for index in range(len(result)):\n",
    "                    result.append(result[index] + 1)\n",
    "\n",
    "        return result[:n+1]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBits(self, n: int) -> List[int]:\n",
    "        dp=[[] for _ in range(18)]\n",
    "        dp[0]=[0]\n",
    "        dp[1]=[1]\n",
    "        for i in range(2,18):\n",
    "            dp[i]=dp[i-1]+[j+1 for j in dp[i-1]]\n",
    "        a,b=1,0\n",
    "        while n>=2**a-1:\n",
    "            if n>=2**a-1:\n",
    "                a+=1\n",
    "        b=n+1-2**(a-1)\n",
    "        result=[]\n",
    "        print(a,b)\n",
    "        for t in range(a+1):\n",
    "            if t!=a:\n",
    "                result.extend(dp[t])\n",
    "            else:\n",
    "                result.extend(dp[t][:b])\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBits(self, n: int) -> List[int]:\n",
    "        dp=[[] for _ in range(18)]\n",
    "        dp[0]=[0]\n",
    "        dp[1]=[1]\n",
    "        for i in range(2,18):\n",
    "            dp[i]=dp[i-1]+[j+1 for j in dp[i-1]]\n",
    "        a,b=1,0\n",
    "        while n>=2**a-1:\n",
    "            if n>=2**a-1:\n",
    "                a+=1\n",
    "        b=n+1-2**(a-1)\n",
    "        result=[]\n",
    "        print(a,b)\n",
    "        for t in range(a+1):\n",
    "            if t!=a:\n",
    "                result.extend(dp[t])\n",
    "            else:\n",
    "                result.extend(dp[t][:b])\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBits(self, n: int) -> List[int]:\n",
    "        if n == 0: return [0]\n",
    "        if n == 1: return [0,1]\n",
    "\n",
    "        result = [0,1]\n",
    "        n_Bin = bin(n)\n",
    "        n_BinLen = len(n_Bin) - 2\n",
    "\n",
    "        for bit in range(1,n_BinLen+1):\n",
    "            if bit == 1:\n",
    "                pass\n",
    "            else:\n",
    "                for index in range(len(result)):\n",
    "                    result.append(result[index] + 1)\n",
    "\n",
    "        return result[:n+1]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBits(self, n: int) -> List[int]:\n",
    "        # DP\n",
    "        res = [0]\n",
    "        while len(res) <= n:\n",
    "            for i in range(len(res)):\n",
    "                res.append(res[i]+1)\n",
    "        return res[:n+1]\n",
    "\n",
    "        # 内置公式\n",
    "        return [bin(i).count('1') for i in range(n+1)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBits(self, n: int) -> List[int]:\n",
    "        i = 0\n",
    "        a = [0, 1]\n",
    "        if n == 0:\n",
    "            return [0]\n",
    "        if n == 1:\n",
    "            return [0,1]\n",
    "        while 2**(i+1) < n:\n",
    "            b = []\n",
    "            for j in a:\n",
    "                b.append(j+1)\n",
    "            a = a + b\n",
    "            i += 1\n",
    "        res = 2**i + 1\n",
    "        print(res)\n",
    "        j = 0\n",
    "        while res <=n:\n",
    "            a.append(a[j]+1)\n",
    "            res += 1\n",
    "            j += 1\n",
    "        return a[:(n+1)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBits(self, n: int) -> List[int]:\n",
    "        if n == 0: return [0]\n",
    "        if n == 1: return [0,1]\n",
    "\n",
    "        result = [0,1]\n",
    "        n_Bin = bin(n)\n",
    "        n_BinLen = len(n_Bin) - 2\n",
    "\n",
    "        for bit in range(1,n_BinLen+1):\n",
    "            if bit == 1:\n",
    "                pass\n",
    "            else:\n",
    "                for index in range(len(result)):\n",
    "                    result.append(result[index] + 1)\n",
    "\n",
    "        return result[:n+1]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "mn = 10 ** 5 + 1\n",
    "s = [0] * mn\n",
    "for i in range(mn):\n",
    "    s[i] = bin(i).count('1')\n",
    "\n",
    "class Solution:\n",
    "    def countBits(self, n: int) -> List[int]:\n",
    "        return s[:n + 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBits(self, n: int) -> List[int]:\n",
    "        ans =list(range(0,n+1))\n",
    "        for i in range(0, len(ans)):\n",
    "            \n",
    "            if i % 2 == 0 :        #偶数\n",
    "                ans[i] = ans[i//2] \n",
    "            else:                  #奇数\n",
    "                ans[i] = ans[(i-1)]+1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBits(self, n: int) -> List[int]:\n",
    "        a=list(range(n+1))\n",
    "        for i in range(len(a)):\n",
    "            a[i]=bin(a[i])\n",
    "            a[i]=str(a[i]).count(\"1\")\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBits(self, n: int) -> List[int]:\n",
    "        if n == 0:\n",
    "            return [0]\n",
    "        if n == 1:\n",
    "            return [0,1]\n",
    "        if n == 2:\n",
    "            return [0,1,1]\n",
    "        power = 2\n",
    "        res = [0,1,1]\n",
    "        for i in range(3, n+1):\n",
    "            sum = 0\n",
    "            while(power * 2 <= i):\n",
    "                power = power * 2\n",
    "            sum = 1 + res[i - power]\n",
    "            res = res + [sum]\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBits(self, n: int) -> List[int]:\n",
    "        if n==0:\n",
    "            return [0]\n",
    "        elif n==1:\n",
    "            return [0, 1]\n",
    "        ans = [0, 1]\n",
    "        while len(ans) <= n:\n",
    "            ans += [i+1 for i in ans]\n",
    "        return ans[:n+1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBits(self, n: int) -> List[int]:\n",
    "        f = [[], [0, 1]] # n = 1\n",
    "        i = 1\n",
    "        j = 2\n",
    "        res = [0, 1]\n",
    "        while j < n+1:\n",
    "            i += 1\n",
    "            tmp = []\n",
    "            for k in range(1, i):\n",
    "                tmp += [x+1 for x in f[k]]\n",
    "            f.append(tmp)\n",
    "            res = res + f[i]\n",
    "            j = j + len(f[i])\n",
    "        return res[:n+1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBits(self, n: int) -> List[int]:\n",
    "        res = [0, 1]\n",
    "        if  n <= 1:\n",
    "            return res[:n+1]\n",
    "        rec = [1,2]\n",
    "        new_rec = [1,2,2,3]\n",
    "        n = n - 1\n",
    "        while n:\n",
    "            p = len(rec)\n",
    "            if n == p:\n",
    "                res = res + rec\n",
    "                return res\n",
    "            elif n > p:\n",
    "                res = res + rec\n",
    "                rec = new_rec\n",
    "                new_rec = rec + [ i + 1 for i in rec]\n",
    "                n = n - p\n",
    "            else:\n",
    "                res = res + rec[:n]\n",
    "                return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBits(self, n: int) -> List[int]:\n",
    "        if n == 0:\n",
    "            return [0]\n",
    "        if n == 1:\n",
    "            return [0, 1]\n",
    "        start, digit, count = 1, 1, 1\n",
    "        a = n\n",
    "        while a > count:\n",
    "            a -= start\n",
    "            start += pow(2, digit)\n",
    "            digit += 1\n",
    "        ir = [1]\n",
    "        final = [0, 1]\n",
    "        for i in range(digit - 1):\n",
    "            final += ir + [j + 1 for j in ir]\n",
    "            ir += [j + 1 for j in ir]\n",
    "        return final[: n + 1]\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
